In an audio signal, for example, a sound is sampled and quantized on the basis of a sampling theorem so as to digitalize the sound through linear pulse coding. In particular, music software is digitalized in a manner that enormously high sound quality is maintained. On the other hand, such digitalized data is easily duplicable in a complete format. Therefore, there has been an attempt to embed copyright information and the like into music software in a format which is imperceptible by a human. As a method for appropriately embedding information into music software of which high-quality sound is demanded, a method for embedding information into a frequency component has been widely employed.
Further, an example of the related art is an information embedding device that varies compression code sequence, without changing the data quantity of the compression code sequence where image data are subjected to compression coding, in such a way that the data are not visually available. Such information embedding device decodes a compression code sequence for each block so as to generate a coefficient block. The information embedding device selects embedded data, which corresponds to the generated coefficient block and a bit value of input data, from an embedded data table and generates a new block, of which the total code length is unchanged, so as to embed other information. Such technique has been disclosed in Japanese Laid-open Patent Publication No. 2002-344726 and Kineo Matsui “Basic Knowledge of Digital Watermark”, Morikita publishing Co. Ltd, pp. 184-194, for example.